Volume rendering is a known technique for visualizing three-dimensional space-filling, or volumetric, data. In general, volume rendering assigns to each point within the volume of data an opacity and a luminosity. The opacity and luminosity are assigned as some function of the data value at that point. Subsequently, there is produced an image of the resulting imaginary solid translucent object. By proper choices of colors, opacities, and viewing directions a visualization and, hence, an understanding of the data may be obtained.
Traditionally, most applications have operated with data sampled onto a uniform or regular grid, such as medical computerized tomography images. Volume rendering of regular grids is readily accomplished by compositing successive layers of volume elements, or voxels, to obtain an image. However, many scientific simulations are accomplished with irregular grids, in which the volume of interest is divided into a space-filling mesh of cells where the data values are computed only at the vertices where the cells meet. Data values within a cell are interpolated from the data values at the vertices of the cell. As one example, and as illustrated in FIG. 9, an irregular grid comprised of cells 1 may be employed for modelling airflow over a curved surface of an aircraft wing 2. The grid is made irregular by conforming the grid to the surface under study. Of course, this is but one example of an irregular grid structure.
The relatively simple compositing method does not apply to rendering such irregular grid data because the thickness of each cell, as viewed from each pixel at the image plane, must be taken into account in forming the image. Rendering such irregular-grid volume data currently requires either resampling the data on a regular grid or using a ray tracing technique.
Unfortunately, neither of these conventional approaches provides an optimum rendering solution. Resampling and rendering the data onto a regular grid typically greatly increases the number of data points to be processed. Ray tracing is also a computationally expensive technique in which imaginary viewing rays are projected out from the image plane. The luminosity and opacity are computed at each cell, taking cell thickness into account, and are then integrated along each ray.
The following U.S. patents are cited for showing conventional regular grid volume rendering systems.
U.S. Pat. No. 4,866,612, issued Sep. 12, 1989, entitled "Imaging System Including Means to Provide A Display Image with Shadows and Three Dimensional Perspectives by a Combination of Voxel and Surface Method" to Takagi et al. relates to displaying surfaces derived from a volumetric regular grid.
U.S. Pat. No. 4,827,413, issued May 2, 1989, entitled "Modified Back-To-Front Three Dimensional Reconstruction Algorithm" to Baldwin et al. describes a method for displaying opaque solids defined by a volumetric regular grid.
U.S. Pat. No. 4,719,585, issued Jan. 12, 1988, entitled "Dividing Cubes System and Method for the Display of Surface Structures Contained within the Interior Region of a Solid Body" to Cline et al. renders a surface defined by a threshold value on a regular volumetric (parellelopiped) grid.
U.S. Pat. No. 4,835,688, issued May 30, 1989, entitled "Three-Dimensional Image Processing Apparatus" to Kimura renders a surface defined by a threshold value on a regular volumetric grid.
U.S. Pat. No. 4,821,210 issued Apr. 11, 1989, entitled "Fast Display of Three-Dimensional Images" to Rumbaugh extracts a surface in the form of a set of triangles directly from volume elements. Specific mention is made of extracting polygonal surfaces from cubes.
U.S. Pat. No. 4,729,098, issued Mar. 1, 1988, entitled "System and Method Employing Nonlinear Interpolation for the Display of Surface Structures Contained Within the Interior Region of a Solid Body" to Cline et al. extracts a surface in the form of a set of triangles directly from the volume elements. This patent also considers only regular grids and has disclosure directed to extracting polygonal surfaces.
An article entitled "Chem-Ray: A Molecular Graphics Program Featuring an Umbra and Penumbra shadowing Routine" by J. W. Lauher, J. Mol. Graphics, 1990, Vol. 8, March pp. 34-38 uses a ray tracing technique to render shadowed molecular graphics models.
Also of interest in this area is U.S. Pat. No. 4,835,712, issued May 30, 1989, entitled "Methods and Apparatus for Imaging Volume Data with Shading" to Drebin et al. This patent describes a method of assigning material opacities to volume elements so as to make boundaries within volumetric data visible. Drebin's teaching makes mention of storing data in arrays of voxels, implying regular grids. Drebin et al. describe a method for computing opacities and luminosities at each point in the volumetric data, but do not specify how the resulting opacities and luminosities are to be rendered for display.
What is not taught by this prior art, and what is thus an object of the invention to provide, is method and apparatus for rendering volumetric data defined at sample points on an irregular grid, such as a mesh of tetrahedra, deformed rectangles, or other non-rectangular volume elements.
It is a further object of the invention to provide an object-based, as opposed to a ray-based, method and apparatus for rendering volumetric data defined at sample points on an irregular grid.
A further object of the invention is to provide an efficient method and apparatus for rendering volumetric data as if the data represented a solid in space having a specific opacity and luminosity at each point, as opposed to only rendering surfaces derived from volumetric data or to rendering the volumetric data as if it were an opaque solid.